// 1. 二叉树的最大深度 深度优先算法（递归）
pub fn max_depth(root: &Vec<i32>, index: usize) -> i32 {
    if let Some(v) = root.get(index) {
        if *v == 0 {
            return 0;
        }
    } else {
        return 0;
    }
    return i32::max(
        max_depth(&root, (index*2)+1),
        max_depth(&root, (index+1)*2))
        + 1;
}

// 1.2 二叉树的最大深度 深度优先算法（非递归）
pub fn traversal(root: &Vec<i32>) -> usize {
    let mut stack: Vec<usize> = vec![];
    let mut index: usize = 0;
    let mut r: usize = 0;
    stack.push(index);
    let mut max_length = 0;
    let mut l_over = false;
    while !(stack.is_empty()) {
        let v_temp = root.get((index * 2) + 1);
        if !l_over &&  v_temp.is_some() && *v_temp.unwrap() != 0 {
            stack.push((index * 2) + 1);
            index = index * 2 + 1;
        } else {
            let v_temp = root.get((index + 1) * 2);
            if v_temp.is_some() && *v_temp.unwrap() != 0 && (index+1)*2 != r {
                stack.push((index+1)*2);
                index = (index+1)*2;
                l_over = false;
            } else {
                if stack.len() > max_length {
                    max_length = stack.len();
                }
                r = index;
                stack.pop();
                if let Some(v) = stack.last() {
                    index = *v;
                }
                l_over = true;
            }
        }
    }
    max_length
}
// 1.3 二叉树的最大深度 广度优先算法（递归）
pub fn bfs(root: &Vec<i32>, index: &mut Vec<Vec<usize>>) -> Vec<Vec<usize>> {
    let mut v: Vec<usize> = vec![];
    for i in index.last().unwrap() {
        let mut temp = root.get((i*2)+1);
        if temp.is_some() && *temp.unwrap() != 0 {
            v.push((i*2)+1);
        }
        temp = root.get((i+1)*2);
        if temp.is_some() && *temp.unwrap() != 0 {
            v.push((i+1)*2);
        }
    }
    if v.is_empty() {
        return index.to_vec()
    }
    index.push(v);
    return bfs(&root, index)
}
// 1.4 二叉树的最大深度 广度优先算法（非递归）
pub fn level_order(root: &Vec<i32>) -> i32 {
    let mut queue: Vec<usize> = vec![0];
    let mut depth = 0;
    while !queue.is_empty() {
        depth += 1;
        let mut v: Vec<usize> = vec![];
        for i in queue {
            let mut temp = root.get((i*2)+1);
            if temp.is_some() && *temp.unwrap() != 0 {
                v.push((i*2)+1);
            }
            temp = root.get((i+1)*2);
            if temp.is_some() && *temp.unwrap() != 0 {
                v.push((i+1)*2);
            }
        }
        queue = v;
    }
    depth
}

// 2. binary search tree (verify)
pub fn is_valid_bst(root: &Vec<i32>) -> bool {
    if root.is_empty() {
        return false;
    }
    return is_bst(&root, 0, std::i32::MIN, std::i32::MAX)
}
fn is_bst(root: &Vec<i32>, index: usize, min: i32, max: i32) -> bool {
    let temp = root.get(index);
    if temp.is_none() || *temp.unwrap() == 0 {
        return true;
    }
    let value = *temp.unwrap();
    if min >= value || max <= value {
        return false;
    }
    return is_bst(&root, index*2+1, min, value) && is_bst(&root, (index+1)*2, value, max)
}
// 3. binary search tree (search)
pub fn search_bst_recursive(root: &Vec<i32>, index: usize, value: i32) -> Option<usize> {
    let temp = root.get(index);
    if temp.is_none() || *temp.unwrap() == 0 {
        return None;
    }
    let value_temp = *temp.unwrap();
    return if value < value_temp {
        search_bst_recursive(&root, index * 2 + 1, value)
    } else if value > value_temp {
        search_bst_recursive(&root, (index + 1) * 2, value)
    } else {
        Some(index)
    }
}
pub fn search_bst_iteration(root: &Vec<i32>, value: i32) -> Option<usize> {
    let mut index = 0 as usize;
    let mut temp = root.get(index);
    let mut temp_value;
    while temp.is_some() && *temp.unwrap() != 0 {
        temp_value = *temp.unwrap();
        if value == temp_value {
            return Some(index);
        } else if value < temp_value {
            index = index*2+1;
            temp = root.get(index);
        } else {
            index = (index+1)*2;
            temp = root.get(index);
        }
    }
    return None;
}

// 4. binary search tree (delete)
pub fn delete_node_backward(mut root: &mut Vec<i32>, index: usize, key: i32) -> Option<usize> {
    let temp = root.get(index);
    if temp.is_none() || *temp.unwrap() == 0 {
        return None;
    }
    let temp_value = *temp.unwrap();
    if key < temp_value {
        delete_node_backward(&mut root, index*2+1, key);
    }
    if key > temp_value {
        delete_node_backward(&mut root, (index+1)*2, key);
    };
    let temp = root.get((index+1)*2);
    if temp.is_none() || *temp.unwrap() == 0 {
        return Some(index*2+1);
    }
    let temp = root.get(index*2+1);
    if temp.is_none() || *temp.unwrap() == 0 {
        return Some((index*2)+1);
    }
    let mut min_index = (index+1)*2;
    let mut temp = root.get(min_index*2+1);
    while temp.is_some() && *temp.unwrap() != 0 {
        min_index = min_index*2+1;
        temp = root.get(min_index*2+1)
    }
    root[index] = root[min_index];
    root[min_index] = 0;
    return Some(min_index);
}
// 4.1
pub fn delete_node_forward(mut root: &mut Vec<i32>, index: usize, key: i32) -> Option<usize> {
    let temp = root.get(index);
    if temp.is_none() || *temp.unwrap() == 0 {
        return None;
    }
    let temp_value = *temp.unwrap();
    if key < temp_value {
        delete_node_forward(&mut root, index*2+1, key);
    }
    if key > temp_value {
        delete_node_forward(&mut root, (index+1)*2, key);
    }
    let temp = root.get((index*2)+1);
    if temp.is_none() || *temp.unwrap() == 0 {
        return Some((index+1)*2);
    }
    let temp = root.get((index+1)*2);
    if temp.is_none() || *temp.unwrap() == 0 {
        return Some((index*2)+1);
    }
    let mut min_index = (index*2)+1;
    let mut temp = root.get((min_index+1)*2);
    while temp.is_some() && *temp.unwrap() != 0 {
        min_index = (min_index+1)*2;
        temp = root.get((min_index+1)*2)
    }
    root[index] = root[min_index];
    root[min_index] = 0;
    return Some(min_index);
}

// 5. binary tree (balanced)
pub fn is_balanced(root: &Vec<i32>, index: usize) -> bool {
    let temp = root.get(index);
    if temp.is_none() || *temp.unwrap() == 0 {
        return true;
    }
    if !is_balanced(&root, index*2+1) || !is_balanced(&root, (index+1)*2) {
        return false;
    }
    let l_depth = max_depth(&root, index*2+1) + 1;
    let r_depth = max_depth(&root, (index+1)*2) + 1;
    if i32::abs(l_depth - r_depth) > 1 {
        return false;
    }
    true
}

// 6. complete binary tree (node counts)
pub fn count_nodes(root: &Vec<i32>, index: usize) -> i32 {
    let temp = root.get(index);
    if temp.is_none() || *temp.unwrap() == 0 {
        return 0;
    }
    return count_nodes(&root, index*2+1) + count_nodes(&root, (index+1)*2) + 1
}
// 6.1
pub fn count_nodes_typical(root: &Vec<i32>, index: usize) -> i32 {
    let temp = root.get(index);
    if temp.is_none() || *temp.unwrap() == 0 {
        return 0;
    }
    let left = count_level(&root, index*2+1);
    let right = count_level(&root, (index+1)*2);
    if left == right {
        return count_nodes_typical(&root, (index+1)*2) + (1 << left);
    } else {
        return count_nodes_typical(&root, index*2+1) + (1 << right);
    }
}
fn count_level(root: &Vec<i32>, index: usize) -> i32 {
    let mut level = 0;
    let mut temp = root.get(index);
    let mut index = index;
    while temp.is_some() && *temp.unwrap() != 0 {
        level += 1;
        index = index*2+1;
        temp = root.get(index);
    }
    level
}
